package weekMatch.two_101;

public class LeeCode_04 {
    public static void main(String[] args) {
        System.out.println(findShortestCycle(7, new int[][]{{0, 1},
                {1, 2}, {2, 0}, {3, 4}, {4, 5}, {5, 6}, {6, 3}}));
        System.out.println(findShortestCycle(4, new int[][]{{0,1},{0,2}}));
        System.out.println(findShortestCycle(5, new int[][]{{0,2},{2,4},{4,0}}));
        System.out.println(findShortestCycle(8, new int[][]{{1,3},{3,5},{5,7},{7,1},{0,2},{2,4},{4,0}}));
    }

    private static int findShortestCycle(int n, int[][] edges) {
        int[] min = new int[]{Integer.MAX_VALUE};
        f(edges, -1, 1, 0, min, -1);
        return min[0] == Integer.MAX_VALUE ? -1 : min[0];
    }

    private static void f(int[][] edges, int start, int len, int index, int[] min, int pre) {
        if (index >= edges.length)
            return;
        if (pre == -1) {
            pre = edges[index][0];
            start = edges[index][0];
        }
        if (edges[index][0] != pre){
            f(edges, edges[index][0], 1, index + 1, min, edges[index][1]);
        }else {
            if (edges[index][0] == pre){
                if (edges[index][1] == start) {
                    min[0] = Math.min(len, min[0]);
                    f(edges, -1, 1, index + 1, min, -1);
                }else {
                    f(edges, start, len + 1, index + 1, min, edges[index][1]);
                }
            }else {
                f(edges, -1, 1, index + 1, min, -1);
            }
        }
    }
}
